package TreeSeries;

import java.util.Stack;

public class IsValidBSTSolution_98 {
    // 递归
    TreeNode max;

    public boolean isValidBST_DFS(TreeNode root) {
        if (root == null) {
            return true;
        }
        // 左
        boolean left = isValidBST_DFS(root.left);
        if (!left) {
            return false;
        }
        // 中
        if (max != null && root.val <= max.val) {
            return false;
        }
        max = root;
        // 右
        boolean right = isValidBST_DFS(root.right);
        return right;
    }

    public boolean isValidBST_BFS(TreeNode root) {
        Stack<TreeNode> stack = new Stack<>();
        TreeNode pre = null;
        if (root != null)
            stack.add(root);

        while (!stack.isEmpty()) {
            TreeNode curr = stack.peek();

            if (curr != null) {
                stack.pop();
                if (curr.right != null)
                    stack.add(curr.right);
                stack.add(curr);
                stack.add(null);
                if (curr.left != null)
                    stack.add(curr.left);
            } else {
                stack.pop();
                TreeNode temp = stack.pop();
                if (pre != null && pre.val >= temp.val)
                    return false;
                pre = temp;
            }
        }
        return true;
    }
}
